package writtenTraining.day47;

import java.util.*;


/**
 * day47(1)：模拟 + 数学：BC138 矩阵转置
 */

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        // 数学 + 模拟
        // 输入数据
        Scanner in = new Scanner(System.in);
        int row = in.nextInt(), col = in.nextInt();
        int[][] nums = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                nums[i][j] = in.nextInt();
            }
        }

        // 转置
        int[][] ret = new int[col][row];

        for (int i = 0; i < col; i++) {
            for (int j = 0; j < row; j++) {
                ret[i][j] = nums[j][i];
            }
        }

        // 输出
        for (int i = 0; i < col; i++) {
            for (int j = 0; j < row - 1; j++) {
                System.out.print(ret[i][j] + " ");
            }

            System.out.println(ret[i][row - 1]);
        }
    }
}


/**
 * day47(2)：dfs + 剪枝：四个选项
 */


class Main2 {
    public static long ret = 0;
    public static int[] count ;
    public static int[] nums;
    public static boolean[][] vim;
    public static void main(String[] args) {
//        dfs + 剪枝
//         输入数据
        Scanner in =new Scanner(System.in);
        count = new int[5];
        for(int i = 1; i < 5; i++) {
            count[i] = in.nextInt();
        }
        nums = new int[13];
        int k = in.nextInt();
        vim = new boolean[13][13];
        while(k-- > 0) {
            int x = in.nextInt(), y = in.nextInt();
            vim[x][y] = true;
            vim[y][x] = true;
        }

        dfs(1);

        System.out.println(ret);
    }

    public static void dfs(int pos) {
//         递归出口
        if(pos > 12) {
            ret++;
            return;
        }

        for(int i = 1; i <= 4; i++) {
//             剪枝
            if(count[i] <= 0) {
//                从这个位置
                continue;
            }

            if (!checkSame(pos,i)) {
//                不符合条件直接减枝
                continue ;
            }

            nums[pos] = i;
            count[i]--;
//            到底下一层
            dfs(pos + 1);
            count[i]++;

        }
    }


    private static boolean checkSame(int pos,int num) {
        for(int i = 0; i < pos;i++) {
//            vim[i][pos] 表示有重复条件
//            num[i] 则是用来判断不满足的情况
            if (vim[i][pos] && nums[i] != num) {
                return false;
            }
        }

        return true;
    }
}


/**
 * day47(3):前缀和 + 数学：42. 接雨水（leetcode）
 */


class Solution {
    public int trap(int[] height) {
        // 前缀和 + 数学

//       预处理
        int n = height.length;
        int[] left = new int[n+1];
        int[] right = new int[n + 1];


        // 统计 0 ~ i + 1 的最大值
        for(int i = 1; i <= n; i++) {
            left[i] = Math.max(left[i-1],height[i-1]);
        }

        // 统计 i ~ n - 1的最大值
        for(int i = n - 1; i >= 0 ; i--) {
            right[i] = Math.max(right[i+1],height[i]);
        }

        // 统计每个柱子最大盛水量
        int ret = 0;
        for(int i = 0; i < n; i++) {
            ret += (Math.min(left[i + 1],right[i]) - height[i]);
        }

        return ret;
    }
}